home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / util / Dictionary.h < prev    next >
C/C++ Source or Header  |  1994-08-01  |  13KB  |  356 lines
  1. /*    $Header: /usr/people/sam/fax/util/RCS/Dictionary.h,v 1.8 1994/02/28 14:23:46 sam Rel $ */
  2. /*
  3.  * Copyright (c) 1990, 1991, 1992, 1993, 1994 Sam Leffler
  4.  * Copyright (c) 1991, 1992, 1993, 1994 Silicon Graphics, Inc.
  5.  *
  6.  * Permission to use, copy, modify, distribute, and sell this software and 
  7.  * its documentation for any purpose is hereby granted without fee, provided
  8.  * that (i) the above copyright notices and this permission notice appear in
  9.  * all copies of the software and related documentation, and (ii) the names of
  10.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  11.  * publicity relating to the software without the specific, prior written
  12.  * permission of Sam Leffler and Silicon Graphics.
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  15.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  16.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  17.  * 
  18.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  19.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  20.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  21.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  22.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  23.  * OF THIS SOFTWARE.
  24.  */
  25. #ifndef _Dictionary_
  26. #define    _Dictionary_
  27.  
  28. // $Revision: 1.8 $
  29. // $Date: 1994/02/28 14:23:46 $
  30. #include "Types.h"
  31. #include "Array.h"
  32. #include "Str.h"
  33. #include "DSmacros.h"
  34. #include "stdlib.h"
  35.  
  36. class fxDictIter;
  37. class fxDictionary;
  38.  
  39. /*******************************************
  40. //  fxDictionary interface
  41. class DICT(KEY,VALUE) : public fxDictionary {
  42. public:
  43.     DICT();
  44.     DICT(DICT const &);
  45.     virtual ~DICT();
  46.     u_int size() const;
  47.     u_int getKeySize() const;
  48.     u_int getValueSize() const;
  49.     void operator=(DICT const &);
  50.     void add(KEY const &,VALUE const &);
  51.     void append(DICT const &);
  52.     void remove(KEY);
  53.     VALUE *cut(KEY);                // does a find & remove
  54.     VALUE *find(KEY const &, KEY **k = 0) const;
  55.     // returns null if not found, optionally returns pointer to key
  56.     VALUE &operator[](KEY const &) const;    // creates the key/value if not
  57.     fxObj *copy() const;
  58. protected:
  59.     virtual u_long hashKey(void const *) const;
  60.     virtual int compareKeys(void const *, void const *) const; // 0 => equal
  61.     virtual void copyKey(void const *, void *) const;
  62.     virtual void copyValue(void const *, void *) const;
  63.     virtual void destroyKey(void *) const;
  64.     virtual void destroyValue(void *) const;
  65.     virtual void createValue(void *) const;
  66. }
  67.  
  68. class DICTIter(DICT,KEY,VALUE) : public fxDictIter {
  69. public:
  70.     DICTIter();
  71.     DICTIter(DICT const &);
  72.     operator=(DICT const &);
  73.     operator++();
  74.     operator++(int);
  75.     operator KEY const &() const
  76.     KEY const &key() const;
  77.     VALUE &value() const;
  78.     fxBool removed();
  79.     fxBool notDone();
  80. }
  81. *******************************************/
  82.  
  83. //----------------------------------------------------------------------
  84.  
  85. class fxDictBucket {
  86. public:
  87.     fxDictBucket(void *kv,fxDictBucket *n) {kvmem=kv; next=n;}
  88.     ~fxDictBucket();
  89.  
  90.     void *kvmem;
  91.     fxDictBucket *next;
  92. };
  93.  
  94. fxDECLARE_PtrArray(fxDictBuckets, fxDictBucket*);
  95. fxDECLARE_PtrArray(fxDictIters, fxDictIter*);
  96.  
  97. //----------------------------------------------------------------------
  98.  
  99. #define fxDictVirtuals(HOW)                        \
  100.     virtual u_long hashKey(void const *) const;                \
  101.     virtual int compareKeys(void const *, void const *) const HOW;    \
  102.     virtual void copyKey(void const *, void *) const HOW;        \
  103.     virtual void destroyKey(void *) const;                \
  104.     virtual void copyValue(void const *, void *) const HOW;        \
  105.     virtual void destroyValue(void *) const;                \
  106.     virtual void createValue(void *) const HOW;                \
  107. __enddef__
  108.  
  109. //----------------------------------------------------------------------
  110.  
  111. class fxDictionary : public fxObj {
  112.     friend class fxDictIter;
  113. public:
  114.     u_int size() const { return numItems; }
  115.     u_int getKeySize() const { return keysize; }
  116.     u_int getValueSize() const { return valuesize; }
  117.     virtual char const *className() const = 0;
  118.  
  119. protected:
  120.     fxDictionary(u_int ksize, u_int vsize, u_int initsize=0);
  121.     fxDictionary(const fxDictionary &);
  122.     virtual ~fxDictionary();
  123.  
  124.     void cleanup();
  125.  
  126.     void operator=(fxDictionary const &);
  127.  
  128.     void *find(void const *, void **k = 0) const;
  129.     void *findCreate(void const *);
  130.     void remove(void const *);
  131.     void *cut(void const *);
  132.  
  133.     virtual void addInternal(void const *,void const *);
  134.  
  135.     fxDictVirtuals(= 0)
  136.  
  137.     void addIter(fxDictIter *);
  138.     void removeIter(fxDictIter *);
  139.     void invalidateIters(fxDictBucket const *) const;
  140.  
  141.     u_int numItems;
  142.     u_int keysize;
  143.     u_int valuesize;
  144.     fxDictBuckets buckets;
  145.     fxDictIters iters;
  146. };
  147.  
  148. //----------------------------------------------------------------------
  149.  
  150. class fxDictIter {
  151.     friend class fxDictionary;
  152. public:
  153.     fxDictIter();
  154.     ~fxDictIter();
  155.     fxDictIter(fxDictionary&);
  156.     void operator=(fxDictionary&);    // not a const argument!
  157.     void operator++()       { increment(); }
  158.     void operator++(int)   { increment(); }
  159.     fxBool removed() const { return invalid; }
  160.     fxBool notDone() const { return node != 0; }
  161. protected:
  162.     void *getKey() const;
  163.     void *getValue() const;
  164.  
  165.     void increment();
  166.     void advanceToValid();
  167.  
  168.     // this is 0 if iterator isn't valid yet.
  169.     fxDictionary *dict;
  170.     u_int bucket;        
  171.  
  172.     // this is 1 if the element was deleted.
  173.     u_int invalid:1;
  174.  
  175.     // If "invalid", this points to the next node. If 0, there are no more nodes
  176.     fxDictBucket *node; 
  177. };
  178.  
  179. //----------------------------------------------------------------------
  180. // Iterator declaration & implementation macros
  181.  
  182. #define fxDECLARE_DictIter(DICT,KEY,VALUE)                \
  183. class fxCAT(DICT,Iter) : public fxDictIter {/*XXX*/            \
  184. public:                                    \
  185.     fxCAT(DICT,Iter)();                            \
  186.     fxCAT(DICT,Iter)(DICT &);                        \
  187.     fxCAT(DICT,Iter)(DICT *);                        \
  188.     void operator=(DICT& d)    /* not a const argument! */        \
  189.     { fxDictIter::operator=(d); }                    \
  190.     void operator=(DICT* d)    /* not a const argument! */        \
  191.     { fxDictIter::operator=(*d); }                    \
  192.     operator KEY const &() const                    \
  193.     { return *(KEY *)fxDictIter::getKey(); }            \
  194.     KEY const &key() const                        \
  195.     { return *(KEY *)fxDictIter::getKey(); }            \
  196.     VALUE &value() const                        \
  197.     { return *(VALUE *)fxDictIter::getValue(); }            \
  198. };                                    \
  199. __enddef__
  200.  
  201. #define fxIMPLEMENT_DictIter(DICT,KEY,VALUE)                \
  202.     fxCAT(DICT,Iter)::fxCAT(DICT,Iter)() : fxDictIter()    {}        \
  203.     fxCAT(DICT,Iter)::fxCAT(DICT,Iter)(DICT &d)                \
  204.     : fxDictIter((fxDictionary &)d) {}                \
  205.     fxCAT(DICT,Iter)::fxCAT(DICT,Iter)(DICT *d)                \
  206.     : fxDictIter(*(fxDictionary *)d) {}                \
  207. __enddef__
  208.  
  209. //----------------------------------------------------------------------
  210. // Dictionary declaration macros
  211.  
  212. #define    fxNOTHING
  213. #define fxDECLARE_Dictionary(DICT,KEY,VALUE)                \
  214. class DICT : public fxDictionary {/*XXX*/                \
  215. public:                                    \
  216.     DICT(u_int initsize=0);                        \
  217.     ~DICT();                                \
  218.     virtual char const *className() const;                \
  219.     void operator=(DICT const &d)                    \
  220.     {fxDictionary::operator=((fxDictionary const&)d);}        \
  221.     void add(KEY const &k, VALUE const &v) { addInternal(&k,&v); }    \
  222.     VALUE *cut(KEY k)                            \
  223.     { return (VALUE*)fxDictionary::cut(&k); }            \
  224.     void remove(KEY k)                            \
  225.     { fxDictionary::remove(&k); }                    \
  226.     VALUE *find(KEY const &k, KEY **kp = 0) const            \
  227.     { return (VALUE*)fxDictionary::find(&k, (void **)&kp); }    \
  228.     VALUE &operator[](KEY const &k)                    \
  229.     { return *(VALUE*)fxDictionary::findCreate(&k); }        \
  230. protected:                                \
  231.     fxDictVirtuals(fxNOTHING)                        \
  232. };                                    \
  233. fxDECLARE_Ptr(DICT);                            \
  234. fxDECLARE_DictIter(DICT,KEY,VALUE);                    \
  235. __enddef__
  236.  
  237. // StrDictionary: the key is a fxStr object. The
  238. // user only has to define copyValue and destroyValue.
  239.  
  240. #define fxDECLARE_StrKeyDictionary(DICT,VALUE) \
  241.     fxDECLARE_Dictionary(DICT,fxStr,VALUE)
  242. #define fxDECLARE_PtrKeyDictionary(DICT,KEY,VALUE) \
  243.     fxDECLARE_Dictionary(DICT,KEY,VALUE)
  244. #define fxDECLARE_ObjKeyDictionary(DICT,KEY,VALUE) \
  245.     fxDECLARE_Dictionary(DICT,KEY,VALUE)
  246.  
  247. //----------------------------------------------------------------------
  248. // Dictionary method macros.  Used by the implement macros.
  249.  
  250. #define fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  251.     DICT::DICT(u_int initsize) :                    \
  252.         fxDictionary(sizeof(KEY),sizeof(VALUE),initsize) {}         \
  253.     DICT::~DICT() { cleanup(); }                    \
  254.     char const *DICT::className() const { return fxQUOTE(DICT); }    \
  255.     fxIMPLEMENT_DictIter(DICT,KEY,VALUE)                \
  256. __enddef__
  257.  
  258. #define fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE)            \
  259.     fxIMPLEMENT_copyObj(DICT,Key,fxStr)                    \
  260.     fxIMPLEMENT_destroyObj(DICT,Key,fxStr)                \
  261.     u_long DICT::hashKey(void const *key) const                \
  262.     { return ((fxStr const *)key)->hash(); }            \
  263.     int DICT::compareKeys(void const *key1, void const *key2) const    \
  264.     { return ::compare(*(fxStr const *)key1,*(fxStr const *)key2); }\
  265. __enddef__
  266.  
  267. #define fxIMPLEMENT_ObjKeyDictionaryMethods(DICT,KEY,VALUE)        \
  268.     fxIMPLEMENT_copyObj(DICT,Key,KEY)                    \
  269.     fxIMPLEMENT_destroyObj(DICT,Key,KEY)                \
  270.     int DICT::compareKeys(void const *key1, void const *key2) const    \
  271.     { return ((KEY const *)key1)->compare((KEY const *)key2); }    \
  272. __enddef__
  273.  
  274. #define fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE)        \
  275.     fxIMPLEMENT_copyPtr(DICT,Key,KEY)                    \
  276.     fxIMPLEMENT_destroyPtr(DICT,Key,KEY)                \
  277.     u_long DICT::hashKey(void const *key) const                \
  278.     { return u_long(((*(const u_int *)(key)) >> 2)); }        \
  279.     int DICT::compareKeys(void const *key1, void const *key2) const    \
  280.     { return (*(char * const *)key1 - *(char * const *)key2); }    \
  281. __enddef__
  282.  
  283. #define fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE)        \
  284.     fxIMPLEMENT_copyObj(DICT,Value,VALUE);                \
  285.     fxIMPLEMENT_destroyObj(DICT,Value,VALUE);                \
  286.     fxIMPLEMENT_createObj(DICT,Value,VALUE);                \
  287. __enddef__
  288.  
  289. #define fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE)        \
  290.     fxIMPLEMENT_copyPtr(DICT,Value,VALUE);                \
  291.     fxIMPLEMENT_destroyPtr(DICT,Value,VALUE);                \
  292.     fxIMPLEMENT_createPtr(DICT,Value,VALUE);                \
  293. __enddef__
  294.  
  295. //----------------------------------------------------------------------
  296. // Dictionary implementation macros.  These are used by the programmer
  297. // to implement new dictionary types.
  298.  
  299. #define fxIMPLEMENT_Dictionary(DICT,KEY,VALUE)                \
  300.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  301. __enddef__
  302.  
  303. #define fxIMPLEMENT_StrKeyDictionary(DICT,VALUE)            \
  304.     fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE)            \
  305.     fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE)            \
  306. __enddef__
  307.  
  308. #define fxIMPLEMENT_ObjKeyDictionary(DICT,KEY,VALUE)            \
  309.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  310.     fxIMPLEMENT_ObjKeyDictionaryMethods(DICT,KEY,VALUE)            \
  311. __enddef__
  312.  
  313. #define fxIMPLEMENT_PtrKeyDictionary(DICT,KEY,VALUE)            \
  314.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  315.     fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE)            \
  316. __enddef__
  317.  
  318. #define fxIMPLEMENT_ObjValueDictionary(DICT,VALUE)            \
  319.     fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE)            \
  320. __enddef__
  321.  
  322. #define fxIMPLEMENT_PtrValueDictionary(DICT,VALUE)            \
  323.     fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE)            \
  324. __enddef__
  325.  
  326. #define fxIMPLEMENT_ObjKeyObjValueDictionary(DICT,VALUE)        \
  327.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  328.     fxIMPLEMENT_ObjKeyDictionaryMethods(DICT, VALUE)            \
  329.     fxIMPLEMENT_ObjValueDictionaryMethods(DICT, VALUE)            \
  330. __enddef__
  331.  
  332. #define fxIMPLEMENT_StrKeyObjValueDictionary(DICT,VALUE)        \
  333.     fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE)            \
  334.     fxIMPLEMENT_StrKeyDictionaryMethods(DICT, VALUE)            \
  335.     fxIMPLEMENT_ObjValueDictionaryMethods(DICT, VALUE)            \
  336. __enddef__
  337.  
  338. #define fxIMPLEMENT_StrKeyPtrValueDictionary(DICT,VALUE)        \
  339.     fxIMPLEMENT_DictionaryMethods(DICT,fxStr,VALUE)            \
  340.     fxIMPLEMENT_StrKeyDictionaryMethods(DICT,VALUE)            \
  341.     fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE)            \
  342. __enddef__
  343.  
  344. #define fxIMPLEMENT_PtrKeyPtrValueDictionary(DICT,KEY,VALUE)        \
  345.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  346.     fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE)            \
  347.     fxIMPLEMENT_PtrValueDictionaryMethods(DICT,VALUE)            \
  348. __enddef__
  349.  
  350. #define fxIMPLEMENT_PtrKeyObjValueDictionary(DICT,KEY,VALUE)        \
  351.     fxIMPLEMENT_DictionaryMethods(DICT,KEY,VALUE)            \
  352.     fxIMPLEMENT_PtrKeyDictionaryMethods(DICT,KEY,VALUE)            \
  353.     fxIMPLEMENT_ObjValueDictionaryMethods(DICT,VALUE)            \
  354. __enddef__
  355. #endif /* _Dictionary_ */
  356.